#include<bits/stdc++.h>
using namespace std;
		int n = 5; //规格
vector<vector<int>> grid
		{ {0,0,1,1,1}
		 ,{0,0,0,1,0}
		 ,{0,0,0,1,0}
		 ,{0,1,1,1,1}
		 ,{0,0,0,0,0} };
         	//设置我们grid当中的障碍物
		//grid为0表示无障碍物，为1表示有障碍物
		
		//初始化标记矩阵
vector<vector<int>> visited(n, vector<int>(n, 0));
struct node
{
	//对于结点存储的坐标进行初始化
	node(int x, int y):_x(x),_y(y)
	{}
	int _x;
	int _y;
};

bool overBorder(int x,int y,int row,int col){
    if (x<0||x>=col||y<0||y>=row) return true;
    else return false;
}
bool BFS(int startx,int starty,int destx,int desty,int row,int col){ //row col用于确定边界
    //init
    if (startx==destx&&starty==desty){
        return true;
    }
    int move[2][4] = {
        {1,0,-1,0 },
        {0,-1,0,1 }
    };
    queue<node> q;
    q.push(node(startx,starty));

    visited[startx][starty] = 1;//init:起始点标记为已访问，起始点入队，定义移动数组
    //begin bfs
    while(!q.empty()){

        node temp = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int newx = temp._x + move[0][i]; 
            int newy = temp._y + move[1][i];

            if (overBorder(newx,newy,row,col))continue;
            //没越界，看看是否访问过
				cout<<"grid:"<<grid[newx][newy]<<endl;
            if (visited[newx][newy]==0&&grid[newx][newy]==0){//不是障碍物可以入队
                if (newx==destx&&newy==desty) return true;
                //没到 
                q.push(node(newx,newy));
                visited[newx][newy] = 1;
            }
        }
    }
    return false;
}




//测试函数
int main()
{	
	// while (1)
	// {
	//实现的是一个输入起点和终点，返回是否能否到的迷宫

		//cout << "请输入起点坐标 sx,sy  以及终点坐标 dx，dy\n";
		int startx = 0, starty = 0, destx = 4, desty = 4;
		//cin >> startx >> starty >> destx >> desty;
	
	
		cout<<BFS(startx, starty, destx, desty, n, n);
	//}
	return 0;
}
